package com.leecode;

/**
 * 21. 合并两个有序链表
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * 示例：
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 */
public class Leet21 {
	public static void main(String[] args) {
		ListNode l1 = new ListNode(1);
		l1.next = new ListNode(2,new ListNode(4));

		ListNode l2 = new ListNode(1);
		l2.next = new ListNode(3,new ListNode(4));

		new Leet21().mergeTwoLists2(l1, l2);
	}

	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		if (l1==null &&l2==null) {
			return null;
		}
		if (l1==null) {
			return l2;
		}
		if (l2==null) {
			return l1;
		}

		//一看就要双指针+双指针
		ListNode ref1 = l1;
		ListNode ref2 = l2;
		ListNode listNode = null;
		ListNode ref=null;

		while (ref1 != null && ref2 != null) {
			if (ref1.val < ref2.val) {
				if (listNode==null) {
					listNode=new ListNode(ref1.val);
					ref=listNode;
					ref1 = ref1.next;
					continue;
				}
				//延长ref
				ref.next = new ListNode(ref1.val);
				//并把ref指针"右移"
				ref=ref.next;
				ref1 = ref1.next;
			}else{
				if (listNode==null) {
					listNode=new ListNode(ref2.val);
//					ref=listNode;
					ref2 = ref2.next;
					continue;
				}
				//延长ref
				ref.next = new ListNode(ref2.val);
				//并把ref指针"右移"
				ref=ref.next;
				ref2 = ref2.next;
			}
		}

		if (ref1==null) {
			ref.next=ref2;
		}
		if (ref2==null) {
			ref.next=ref1;
		}

		return listNode;
	}

	/**
	 * 58%,89%,recur这么简单,上面我当初是怎么想到双指针(看起来更复杂)的?!!
	 */
	public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
		if(l1==null)return l2;
		if(l2==null)return l1;

		ListNode res=null;
		if(l1.val<l2.val){
			res=new ListNode(l1.val);
			l1=l1.next;
			res.next=mergeTwoLists2(l1.next,l2);
		}else{
			res=new ListNode(l2.val);
			l2=l2.next;
			res.next=mergeTwoLists2(l1,l2.next);
		}

		return res;
	}

	/**
	 * 
	 */
	public ListNode mergeTwoLists3(ListNode l1, ListNode l2) {
		
		return null;
	}
}
